package h0908;

import java.util.HashMap;
import java.util.HashSet;

/**
  * @description 第一个缺失的正整数
  * @author 不知名帅哥
  * @date 2024/9/9 14:51
  * @version 1.0
*/
public class FirstAbsentPositiveInteger {
    public static void main(String[] args) {

    }
    public int firstMissingPositive(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        int n=nums.length;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i]>0&&nums[i]<=n){
                set.add(nums[i]);
            }
        }
        int a=1;
        while (true){
            if (!set.contains(a)){
                return a;
            }
            a++;
        }
    }
    public int firstMissingPositive2(int[] nums) {
        int n = nums.length;

        // 第一步：清理数组，将所有小于等于0或大于n的数值置为n+1
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0 || nums[i] > n) {
                nums[i] = n + 1;
            }
        }

        // 第二步：将出现的正整数对应的索引位置的数值标记为负数
        for (int i = 0; i < n; i++) {
            int num = Math.abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }

        // 第三步：寻找第一个没有被标记为负数的位置
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }

        // 如果所有位置都被标记为负数，则返回n+1
        return n + 1;
    }

}
